Modern electronic systems are often designed with the assistance of electronic computer-aided-design tools, hereinafter referred to as ECAD tools. Typically, a user will capture a schematic diagram or other convenient form of circuit description on a display screen of an ECAD system using any of a number of interactive or automatic (e.g., module generators, silicon compilers, logic synthesizers) techniques widely known in the present art. As a part of the design process, a designer will typically capture and compile a design and then simulate it through the use of a logic simulator.
Complex logic circuits are customarily described hierarchically, but are simulated flat (or fully expanded). This means that if a module A in a user's design contains three instances of a submodule B, and submodule B contains two instances of another submodule C, the user will declare only two copies of submodule C in the process of capturing his design, but because of the implied replication in the user's design, the simulator will simulate six instances of submodule C for each instance of module A, since there are two instances of submodule C in each of the three instances of submodule B comprising module A. When such a circuit description is modified and re-simulated, a program must read the hierarchical description and produce a flat, or fully expanded, description of the hierarchical design before the simulation may be accomplished. A program that accomplishes this function is called a "linker" or "flattener". Hereinafter, the terms "link" and "flatten" will be used interchangeably. All modern ECAD systems include such a program, since a flat circuit description is too cumbersome for users to create directly, and a hierarchical description cannot easily be simulated directly, because the many different instances of the submodules of a hierarchy may be in different states during simulation and must be dealt with individually by the simulator.
Inputs to a linker generally consist of a set of circuit descriptions of different hierarchical levels or "modules" in a circuit. Each module description contains a list of submodules, internal wires (also called "signals" or "nets") , and I/O (input/output) pins. Each I/O pin of the module's submodules is connected to one of the module's internal wires. Some of those wires are in turn connected to I/O pins of the module itself. The details of these interconnections are also a part of the module description. In addition, the module description contains the name of the module, the name of each submodule, internal wire, and I/O pin the module comprises. Any module may itself be a submodule of another module; further illustrating the impact of hierarchy on a design.
These inputs to the linker may be either memory-resident data structures, or data structures contained in files on an on-line mass-storage device. Since it is a relatively trivial process to move data structures between files and memory, it will be assumed hereinafter without loss of generality that all linker inputs are memory-resident.
The output from a linker is a flattened, or expanded, description of the input circuit descriptions. It contains an explicit representation of every copy of every bottom-level submodule in the circuit design. The term "bottom-level submodule" refers to submodules at the bottom level of a circuit hierarchy for which no further expansion is possible, i.e., submodules which comprise no further submodules. Hereinafter, such bottom-level submodules will be referred to interchangeably as "primitives". Each primitive has I/O connections (pins) which are explicitly represented, but which may be replicated in multiple instances of the primitive. Connections between I/O pins of primitives may be made at a higher level of hierarchy where the details of the lower levels of circuit interconnection are not explicitly visible, but which do exist.
Some ECAD systems have special features which complicate the process of linking, or flattening, a design description. Some examples of such features are:
a. Global Signals:
This feature allows wires to pass from one module to another without passing through explicitly declared I/O pins of either module. This is primarily used for "universal" signals such as power supplies and master clocks. Because these connections are "assumed" and not explicitly declared in a circuit description, a linker must deal with these signals in a less straightforward fashion than would otherwise be possible.
b. Primitive modules with variable numbers of I/O pins:
This capability is used mainly for RAM (random access memory) primitives so that one primitive may be used to describe RAMs of many different sizes. An instance of such a primitive would have as part of its description a list of parameters which would affect the number and type of I/O pins on that instance of the primitive. Again, a linker would have to handle this special situation.
c. Primitives with unconnected inputs:
Simple logic gate primitives may have unconnected inputs. For example, a 3-input NAND gate may have one input unconnected. The ECAD system would recognize the condition and compute a 2 input NAND function in its place. The makes it unnecessary to have separate 2-input and 3-input NAND primitives. This situation must be taken into account by a linker.
d. Module I/O pins wired together:
"Feed-through" pins are sometimes allowed by ECAD systems. In these cases, two pins are declared and shown graphically, but are wired together internally. This is usually done as a graphical convenience to the ECAD user. A linker would have to replace two or more nets connected to pins of this type with a single net, since all are connected together in the lower levels of hierarchy.
e. Connections by position and by name:
Some ECAD systems allow wires to be attached either to a submodule pin with a specified name or to a submodule pin in a specified position. If one wire is connected to a pin named "X" and another wire is connected to a pin number 3, it is the responsibility of the linker to determine whether those wires are connected to each other by checking whether pin number 3 is named "X" or not. This requires linker actions similar to those for module pins wired together.
Typically, schematic capture tools use connection by name, while automatic module generators use connection by position. The ability to support both styles would be of value and, as will become evident, is incorporated in the present invention.
Typical linker (or flattener) programs consist of four main processing tasks. These are:
a. Loading the hierarchical design description.
b. Altering the module designs to reflect information about their submodules (such as implicit power connections, multiple pins with the same signal, etc.) which was not previously available. The effect is to explicitly reference any portions of the submodule which would otherwise be considered implicit. This step is not required if certain design restrictions are placed on the design methodology which eliminate the possibility of feed-through connections or "implied" connections where a connection may be made without a user-drawn "wire". This task is performed by using a pin-name list or equivalent data structure to merge signals (also called wires or nets) which are not explicitly connected by a wire, but which are assumed to be connected by name or other convention.
c. Creating copies (instances) of those (sub)module descriptions which are used more than once, i.e., if a module is applied to a circuit design more than once, it is necessary to replicate the module description (or at least those parameters which make an instance of a module unique) so that a subsequent simulation process may treat each instance of the module separately. This is accomplished by scanning the module design and creating a copy each time a module instance is detected; then performing the same operation recursively to the copy. This process creates a flattened representation (or design description) of the input hierarchical design, typically in the form of a tree structure. Typically, the entire module description is not copied for each instance. Instead, each copy will typically contain a reference to the master copy and parameter space for information about explicit connections and internal state. The reference to the original allows information which is common to all instances of a module to be shared, saving time and storage space.
d. Connecting the copies together in accordance with the wiring directions found in each module design. That is, information relating to inter-module connections is stored in the copies of the module descriptions, allowing further processing steps to have full knowledge of signal routing within the circuit design. This task is performed by visiting every submodule I/O pin in the flattened design description, and tracing through the hierarchical design description to find every other I/O pin in the flattened design which connects to it. This involves traversing the various levels of hierarchy from module description to module description, until all interconnections in the flattened design have been resolved. When this process is complete, each group of commonly connected pins will have a "net" assignment, and each module I/O pin will have been marked with the number or name of the net to which it is connected. This task is typically the most time-consuming of the four tasks listed here.
An approach which combines the tasks of creating and connecting copies (c and d, above) is reported by Mentor Graphics Corp. in Paper 39.3 of the 1988 DAC (25th ACM/IEEE Design Automation Conference) Proceedings. This paper describes a technique whereby the module description copies are wired together (i.e., nets are created and I/O pins assigned to them) as the copies are created. The technique provides a substantial performance improvement over the typical process described above, but does not provide for resolution of feed-through pins.
As will become evident hereinafter, the present invention is considerably faster than the Mentor algorithm; only the factor is smaller.
The primary disadvantage of present linking algorithms is that they are slow, and some are inflexible. Engineers typically spend most of their design time in an "Edit-Compile-Simulate" iterative process. After simulating a version of a circuit design, an engineer will typically make a modification which he hopes will improve the circuit performance or correct a problem detected in simulation. He then runs the programs which prepare the circuit for simulation (that is, he "compiles" the circuit), re-simulates, studies the simulation output to determine success or failure of the circuit modifications and determines whether further modifications are required. Any decrease in the time required to prepare a circuit for simulation provides a direct time benefit to the engineer which is experienced as many times as the "Edit-Compile-Simulate" process is repeated.